﻿// 5970. 字符串重组.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://www.acwing.com/problem/content/5973/

对于一个长度不小于 2
 的字符串，我们可以对其使用重组操作。

重组操作分为两个步骤：

将字符串从中间任意位置截断，得到前后两个非空子串。
将两个子串交换位置（前变后，后变前）后重新连接，得到新字符串。
例如，对于字符串 abcdef，一种可行的重组操作为：

将字符串截断为两个非空子串 ab、cdef。
将两个子串交换位置后重新连接，得到新字符串 cdefab。
给定一个起始字符串 s1
 和一个目标字符串 s2
。

我们希望对 s1
 进行恰好 k
 次重组操作后得到 s2
。

请你计算，一共有多少种不同的可行方案。

由于答案可能很大，请你输出对 109+7
 取模后的结果。

对于两种可行方案，如果存在至少一个 i
（1≤i≤k
）满足，在第 i
 次操作中，两种方案的截断位置不同，则认为两种可行方案为不同方案。

输入格式
第一行包含一个由小写字母构成的非空字符串 s1
。

第二行包含一个由小写字母构成的非空字符串 s2
。

第三行包含整数 k
。

输出格式
一个整数，表示不同的可行方案的数量对 109+7
 取模后的结果。

数据范围
前三个测试点满足 2≤|s1|,|s2|≤6
，0≤k≤2
。
所有测试点满足 2≤|s1|,|s2|≤1000
，|s1|=|s2|
，0≤k≤105
。

输入样例1：
ab
ab
2
输出样例1：
1
输入样例2：
ababab
ababab
1
输出样例2：
2
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 